5338. Полный граф - 2

Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную таблицу. В ячейке [i, j] таблицы стоит "1", если граф может получить из фигурки i фигурку j одним сгибом. Иначе там стоит "0". Изначально в руках у графа Дуку чистый лист, то есть фигурка номер x по его системе, сложить же он желает журавлика – фигурку номер y.

Найдите, за сколько операций граф достигнет желаемого.

Вход. В первой строке находится число n (1 ≤ n ≤ 1000). В следующих n строках задана таблица Дуку. В (n + 1) - ой строке стоят числа x и y.

Выход. Выведите минимальное количество операций, которые придется осуществить. Если же коварным планам Графа не суждено осуществиться, выведите "-1".

Пример входа	Пример выхода
4 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 2	3

РЕШЕНИЕ

графы – поиск в ширину

Анализ алгоритма

В задаче необходимо найти наименьшее расстояние от x до y на невзвешенном графе. Это можно совершить при помощи поиска в ширину.

Пример

Приведенный в примере граф имеет вид:

Реализация алгоритма

Объявим матрицу смежности g для хранения графа, dist[i] хранит кратчайшее расстояние от истока до вершины i.

#define MAX 1010

int g[MAX][MAX], used[MAX], dist[MAX];

Поиск в ширину на графе. Заполнение массива кратчайших расстояний dist.

void bfs(int start)

{

memset(used,0,sizeof(used));

memset(dist,-1,sizeof(dist));

dist[start] = 0;

int q[MAX], Head = 0, Tail = 1;

q[Head] = start; used[start] = 1;

while(Head < Tail)

{

int v = q[Head++];

for(int i = 1; i<= n; i++)

if (g[v][i] && !used[i])

{

q[Tail++] = i;

used[i] = 1;

dist[i] = dist[v] + 1;

}

}

}

Читаем входные данные.

scanf("%d",&n);

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

scanf("%d",&g[i][j]);

scanf("%d %d",&x,&y);

Запускаем поиск в ширину из вершины x.

bfs(x);

В зависимости от значения dist[y] выводим ответ.

if (dist[y] == -1) printf("-1\n");

else printf("%d\n",dist[y]);

Реализация алгоритма – STL

#include <cstdio>

#include <vector>

#include <queue>

#include <cstring>

#define MAX 1001

using namespace std;

int i, j, n, a, b;

int g[MAX][MAX], dist[MAX];

void bfs(int start)

{

memset(dist, -1, sizeof(dist));

dist[start] = 0;

queue<int> q;

q.push(start);

while (!q.empty())

{

int v = q.front(); q.pop();

for (int to = 1; to <= n; to++)

if (g[v][to] && dist[to] == -1)

{

q.push(to);

dist[to] = dist[v] + 1;

}

}

}

int main(void)

{

scanf("%d", &n);

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

scanf("%d", &g[i][j]);

scanf("%d %d", &a, &b);

bfs(a);

printf("%d\n", dist[b]);

return 0;

}